// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem503.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=503 lang=cpp
 *
 * [503] 下一个更大元素 II
 *
 * https://leetcode-cn.com/problems/next-greater-element-ii/description/
 *
 * algorithms
 * Medium (64.64%)
 * Likes:    586
 * Dislikes: 0
 * Total Accepted:    129.2K
 * Total Submissions: 199.4K
 * Testcase Example:  '[1,2,1]'
 *
 * 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的
 * 下一个更大元素 。
 *
 * 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1
 * 。
 *
 *
 *
 * 示例 1:
 *
 *
 * 输入: nums = [1,2,1]
 * 输出: [2,-1,2]
 * 解释: 第一个 1 的下一个更大的数是 2；
 * 数字 2 找不到下一个更大的数；
 * 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
 *
 *
 * 示例 2:
 *
 *
 * 输入: nums = [1,2,3,4,3]
 * 输出: [2,3,4,-1,4]
 *
 *
 *
 *
 * 提示:
 *
 *
 * 1 <= nums.length <= 10^4
 * -10^9 <= nums[i] <= 10^9
 *
 *
 */

// @lc code=start
#include <stack>
#include <vector>
#include <iostream>
using namespace std;
class Solution
{
public:
    vector<int> nextGreaterElements(vector<int> &nums)
    {
        int n= nums.size();
        vector<int> ret(n,-1);
        stack<int> s;
        for(int i=0;i<n*2-1;++i){
            while(!s.empty()&&nums[s.top()]<nums[i%n]){
                ret[s.top()]=nums[i%n];
                s.pop();
            }
            s.push(i%n);
        }
        return ret;
    }
};
/* class Solution
{
public:
    vector<int> nextGreaterElements(vector<int> &nums)
    {
        int n = nums.size();
        int flag = 0;
        int i = 0;
        vector<int> ans(n);
        // 分别存储元素值和下标
        stack<pair<int, int>> s;

        while (!s.empty() || flag == 0)
        {
            for (i = 0; i < n; ++i)
            {
                if (!s.empty())
                {
                    if (nums[i] > s.top().first)
                    {
                        while (!s.empty() && nums[i] > s.top().first)
                        {
                            ans[s.top().second] = nums[i];
                            s.pop();
                        }

                    }


                    while(!s.empty()&&nums[i]==s.top().first){
                    // if (nums[i] == s.top().first)

                        if (i > s.top().second)
                        {
                            if (flag == 0)
                            {
                                // s.push({nums[i], i});
                            }
                            else
                            {
                                while (nums[i] == s.top().first)
                                {
                                    ans[s.top().second] = -1;
                                    s.pop();
                                }

                            }
                        }
                        else if (i < s.top().second)
                        {
                            // s.push({nums[i], i});
                        }
                        else
                        {
                            s.pop();
                            ans[i] = -1;
                        }

                    }
                     s.push({nums[i], i});
                }
                if (s.empty() && flag == 0)
                {
                    s.push({nums[i], i});
                    flag = -1;
                }
            }
            flag = 1;
        }
        return ans;
    }
}; */
// @lc code=end
